1. Field of the Invention
This invention relates generally to concurrent access to shared objects, and more particularly to a system and method for implementing a transactional memory that includes multiple, distinct, best effort support mechanisms, integrated in a single transactional memory implementation.
2. Description of the Related Art
The multi-core revolution currently in progress is making it increasingly important for applications to exploit concurrent execution in order to take advantage of advances in technology. In concurrent software designs and implementations, it is often important to ensure that one thread does not observe partial results of an operation that is concurrently being executed by another thread. Such assurances are important for practical and productive software development because without them, it can be extremely difficult to manage the interactions of concurrent threads. Typical concurrent programming practices, such as those based on locks and condition variables, are inadequate for this task. Locks do not compose, and introduce troublesome tradeoffs between complexity, performance, and scalability. Furthermore, locks are subject to deadlock if not used carefully.
Transactional memory is a paradigm that allows the programmer to design code as if multiple locations can be accessed and/or modified in a single atomic step. As typically defined, a transactional memory interface allows a programmer to designate certain sequences of operations as “atomic blocks” and “transactions,” which are guaranteed by the transactional memory implementation to either take effect atomically and in their entirety (in which case they are said to succeed), or have no externally visible effect (in which case they are said to fail). Thus, with transactional memory, it may be possible in many cases to complete multiple operations with no possibility of another thread observing partial results, even without holding any locks, or without the programmer needing to determine what locks should be held, the order in which they are acquired, etc. The transactional memory paradigm can significantly simplify the design of concurrent programs.
Transactional Memory (TM) allows programmers to use transactional or atomic blocks, which may be considered sequential code blocks that should be executed atomically. In other words, executions of atomic blocks by different threads do not appear to be interleaved. To execute an atomic block, the underlying system may begin a transaction, execute the atomic block's memory accesses using that transaction, and then try to commit the transaction (i.e., to attempt to copy back results of the transaction to shared memory). If the transaction commits successfully, the atomic block's execution seems to take effect atomically at the transaction's commit point. If it fails, the execution does not seem to take effect at all and the atomic block might be retried using a new transaction. It is the responsibility of the TM implementation to guarantee the atomicity of operations executed by transactions.
Transactional memory is widely recognized as a promising paradigm for allowing a programmer to make updates to multiple locations in a manner that is apparently atomic, while addressing many of the problems associated with the use of locks. In general, transactional memory can be implemented in hardware (HTM), with the hardware directly ensuring that a transaction is atomic, or in software (STM) that provides the “illusion” that the transaction is atomic, even though in fact it is executed in smaller atomic steps by the underlying hardware. While HTM solutions are generally faster than STM ones, so-called “best effort” HTM implementations may not be guaranteed to be able commit any particular transaction, in which case a programmer cannot rely solely on HTM, even if it is almost always effective.
Typically, systems implement or support only a single type of transactional memory implementation. Most existing transactional memory implementations are designed and optimized for one situation, and may not perform well or be applicable in others, e.g., those in different environments, those with different workloads, etc. Recently developed Hybrid Transactional Memory (HyTM) implementations allow transactions to be executed using hardware transactional memory if it is available and when it is effective, or using software transactional memory otherwise. Hybrid transactional memory techniques are described in U.S. Pat. No. 7,395,382, entitled “Hybrid Software/Hardware Transactional Memory,” and naming Mark S. Moir as inventor, which is herein incorporated by reference in its entirety. In the HyTM implementations described therein, both hardware and software transactions include significant overhead in order to facilitate detection and resolution of conflicts between different types of transactions. In some such implementations, software transactional memories can exploit various “best effort” hardware mechanisms to improve performance when such mechanisms are effective, but can operate without them when they are not. Different best effort mechanisms have been proposed by different organizations. However, if different mechanisms are implemented for different platforms, it will be difficult for programmers to write software that is portable but takes advantage of any best effort mechanisms provided by these different platforms.